// https://github.com/facebook/react/blob/main/packages/scheduler/src/SchedulerMinHeap.js
// 最小堆 通过sortIndex来排序

/**
 * 添加元素
 * @param {*} heap
 * @param {*} node
 */
export function push(heap, node) {
  const index = heap.length;
  // 每次都先添加到尾部
  heap.push(node);
  // 然后向上调整
  siftUp(heap, node, index);
}

// 只是查看
export function peek(heap) {
  const first = heap[0];
  return first === undefined ? null : first;
}

/**
 * 弹出最小堆的堆顶元素
 * @param {*} heap
 * @returns
 */
export function pop(heap) {
  const first = heap[0];
  if (first !== undefined) {
    // 这是数组的方法
    const last = heap.pop();
    if (last !== first) {
      heap[0] = last;
      // 最后一个放在最上面 向下调整
      siftDown(heap, last, 0);
    }
    return first;
  } else {
    return null;
  }
}

/**
 * 向上调整
 * @param {*} heap
 * @param {*} node
 * @param {*} i
 */
export function siftUp(heap, node, i) {
  let index = i;
  while (true) {
    // (index - 1) / 2  >>> 1 这样可以取整
    const parentIndex = (index - 1) >>> 1;
    // 父节点
    const parent = heap[parentIndex];
    // 不需要比较左右的 只要保证最小的在第一位
    if (!!parent && compare(parent, node) > 0) {
      // 父节点比子节点大 就要交换位置
      heap[parentIndex] = node;
      heap[index] = parent;
      index = parentIndex;
    } else {
      return; // 结束
    }
  }
}

/**
 * 向下调整
 * @param {*} heap
 * @param {*} node
 * @param {*} i
 */
export function siftDown(heap, node, i) {
  let index = i;
  const length = heap.length;
  const halfLength = length >>> 1;
  while (index < halfLength) {
    const leftIndex = (index + 1) * 2 - 1;
    const left = heap[leftIndex];
    const rightIndex = leftIndex + 1;
    const right = heap[rightIndex];
    if (compare(left, node) < 0) {
      if (rightIndex < length && compare(right, left) < 0) {
        heap[index] = right;
        heap[rightIndex] = node;
        index = rightIndex;
      } else {
        heap[index] = left;
        heap[leftIndex] = node;
        index = leftIndex;
      }
    } else if (rightIndex < length && compare(right, node) < 0) {
      heap[index] = right;
      heap[rightIndex] = node;
      index = rightIndex;
    } else {
      return;
    }
  }
}

export function compare(a, b) {
  const diff = a.sortIndex - b.sortIndex;
  return diff !== 0 ? diff : a.id - b.id;
}
